Un réseau professionnel (1) - Corrigé

Énoncé

Anna, Benjamin, Colin, Dana, Étienne, François, Giselle, Hadrien, Inès, Jasmine, Kévin et Lola sont tous inscrits sur le même réseau professionnel.

Voici leurs liens relationnels :

• Anna est en relation avec Dana, Giselle, Hadrien et Inès.
• Benjamin est en relation avec Colin, Dana, Étienne, François et Kévin.
  
• François est en relation avec Inès, Jasmine et Lola.
• Kévin est en relation avec Benjamin et Giselle.

1. Représenter ces relations avec un graphe (on pourra utiliser les initiales des prénoms).

2. Ce graphe est-il connexe ?

3. Ce graphe est-il complet ?

4. Donner une chaîne qui relie Colin à Jasmine. 

5. Quelle est la distance (en nombre de liens relationnels) entre Colin et Jasmine ?

Solution

1. 

2. Ce graphe est connexe : aucun individu ou groupe d'individus n'est isolé du reste du groupe.

3. Ce graphe n'est pas complet (il n'y a par exemple pas de relation entre Inès et Hadrien).

4. Une chaîne qui relie Colin à Jasmine : 
Colin - Benjamin - Kévin - Giselle - Anna - Inès - François - Jasmine

5. Pour trouver la distance entre Colin et Jasmine, il faut écrire la matrice d'adjacence  `A`  du graphe et trouver la plus petite puissance où le coefficient (3 ; 10) n'est pas nul.